这章在大纲中是查找的一部分，考察的内容也比较少

4.1 串定义与基本操作

4.1.1 定义


4.1.2 基本操作


求子串


比较


定位


字符集编码


4.1.3 存储结构

顺序存储

 

链式存储


4.2 模式匹配

在主串中寻找模式串相同的子串，并返回位置

4.2.1 朴素模式匹配算法（暴力）


与index算法相同，下面使用另一种方式实现：    这种算法的思想和滑动窗口有点相似 

4.2.2 KMP算法

朴素算法出现不匹配的位置的前面的主串字符的内容是已知的 

 也就是说，在第n个字符匹配失败的时候，仅仅根据模式串的内容就可以确定j指针指向的位置，这与主串无关。对于模式串‘abaabc’：


获得n与j之间的对应关系（next数组），主串的指针就不会回溯，可以大大的提升效率


性能对比


求next数组（手算）

  换言之，无脑写next[1]=0，next[2]=1，剩下的部分分析

求nextval数组（优化next数组）

在这种情况下，i所指的字符一定不是a，j在移动到1后（a），一定会匹配失败 

我们可以直接将next[3]的值改为0，跳过匹配失败的那一步： 

nextval[1]无脑写0，只有匹配失败的字符和其next数组的字符相同时，才会优化：